package ordinaryArray;

import java.util.Arrays;

/**
 * @author kunkun
 * @className LeetCode_238
 * @Description 除自身以外数组的乘积
 * @date 2025/3/5 9:38
 */
public class LeetCode_238 {
    public int[] productExceptSelf(int[] nums) {
//        return solution_1(nums);
        return solution_2(nums);
    }

    public static void main(String[] args) {
        LeetCode_238 object = new LeetCode_238();
        object.printArray(object.productExceptSelf(new int[]{1,2,3,4}));        //24 12 8 6
        object.printArray(object.productExceptSelf(new int[]{-1,1,0,-3,3}));    //0 0 9 0 0
    }

    public void printArray(int[] nums){
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
        System.out.println();
    }



    /**
    * @Description: 方法1:利用前缀和,时间复杂度:O(n),空间复杂度:O(n)
    * @Author: kunkun
    * @Date:  2025/3/5 11:09
    * @Parameters:
    * @Return
    * @Throws
    */
    public int[] solution_1(int[] nums){
        //特殊情况
        if (nums.length<=1){
            return nums;
        }

        //1. 计算前缀和
        int[] pre = new int[nums.length];
        int[] suf = new int[nums.length];
        int[] result = new int[nums.length];
        int value=1;
        for (int i = 0; i <nums.length; i++) {
            value*=nums[i];
            pre[i]=value;
        }
        value=1;
        for (int i = nums.length-1;i >=0; i--) {
            value*=nums[i];
            suf[i]=value;
        }
        //2. 计算返回结果
        for (int i = 0; i < nums.length; i++) {
            if (i==0){
                result[i]=suf[i+1];
            } else if (i== nums.length-1) {
                result[i]=pre[i-1];
            }else{
                result[i]=pre[i-1]*suf[i+1];
            }
        }
        return result;
    }

    /**
    * @Description: 方法2:对前缀和进行优化--将前乘积和后乘积分别乘入目标数组,时间复杂度:O(n),空间复杂度:O(1)
    * @Author: kunkun
    * @Date:  2025/3/5 11:09
    * @Parameters:
    * @Return
    * @Throws
    */
    public int[] solution_2(int[] nums){
        //特殊情况
        if (nums.length<=1){
            return nums;
        }
        //1. 定义变量
        int[] result =  new int[nums.length];
        Arrays.fill(result,1);

        //2. 计算前乘积
        int preSum=1,afterSum=1;
        for (int i = 0; i < nums.length; i++) {
            result[i]*=preSum;
            preSum*=nums[i];
        }

        //3. 计算后乘积
        for (int i = nums.length-1; i >= 0; i--) {
            result[i]*=afterSum;
            afterSum*=nums[i];
        }

        return result;
    }


}
